package com.example.Arithmetic.Lettcode;

/**
 * 日期：2024/1/1
 * 时间：8:41
 * 描述：力扣62题，不同路径
 * 初始化侧边表格，某个单元格值是int[i][j-1]+int[j-1][i]=值
 */
public class E01Lettcode62 {
    public int uniquePaths(int m, int n) {
        int[][] ints = new int[m][n];
//        初始化顶行
        for (int i = 0; i < m; i++) {
            ints[i][0] = 1;
        }
//        初始化顶列
        for (int i = 0; i < n; i++) {
            ints[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                ints[i][j] = ints[i - 1][j] + ints[i][j - 1];
            }
        }
        return ints[m - 1][n - 1];
    }

    //    降维
    public int uniquePathsj(int m, int n) {
        int[] ints = new int[n];
        for (int i = 0; i < n; i++) {
            ints[i] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                ints[j]=ints[j]+ints[j-1];
            }
        }
        return ints[n-1];
    }
}

